package leetcode_1000;

/**
 *@author 周杨
 *BinarySubarraysWithSum_930_ 给一个二进制数组 问有多少子数组加起来和等于s
 *describe:用动态规划 
 *2018年10月28日 上午11:16:07
 */
public class BinarySubarraysWithSum_930_ {
	public static void main(String[] args) {
		BinarySubarraysWithSum_930_ test=new BinarySubarraysWithSum_930_();
		System.out.println(test.numSubarraysWithSum(new int[] {1,0,1,0,1}, 2));
		System.out.println(test.numSubarraysWithSum(new int[] {1,1,1,0,1}, 2));
		System.out.println(test.numSubarraysWithSum(new int[] {0,0,0,0,0}, 0));
	}
	
	public int numSubarraysWithSum(int[] A, int S) {
		if(A.length==0)
			return 0;
		int unconsistent=0;//非连续的S个数
        int dp[]=new int[S+1];
        if(A[0]==0)
        	dp[0]=1;
        else
            if(S>0)
        	    dp[1]=1;
        for(int i=1;i<A.length;++i) {
    		unconsistent+=dp[S];
        	if(A[i]==0) {
        		dp[0]++;//其余的保持不变
        	}
        	else {//可能到达S个
        		for(int j=S;j>0;--j) {
        			dp[j]=dp[j-1];
        		}
        		if(S>0)
        			dp[1]++;//顺便加上自己
        		dp[0]=0;
        	}
        }
        return unconsistent+dp[S];
    }
}
